﻿#include <iostream>
#include <stdlib.h>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

class Solution {
public:
	//查找下一个目的地
	bool findNextStation(vector<vector<string>>& tickets, string laststation, vector<string>& ans, vector<bool> visited) {
		if (ans.size() == tickets.size() + 1)
			return true;
		unordered_map<string, int> nextstation;
		vector<string> vec_next;
		for(int i = 0; i < tickets.size();i++){
			if (tickets[i][0] == laststation) {
				if (tickets[i][0] == laststation && !visited[i]) {
					nextstation[tickets[i][1]] = i;
					vec_next.push_back(tickets[i][1]);
				}
			}
		}
		if (nextstation.size() == 0)
			return false;
		sort(vec_next.begin(), vec_next.end());
		for(int i = 0;i < vec_next.size();i++){
			int k = nextstation[vec_next[i]];
			visited[k] = true;
			ans.push_back(vec_next[i]);
			if (findNextStation(tickets, vec_next[i], ans, visited))
				break;
			else {
				visited[k] = false;
				ans.pop_back();
			}
		}
		if (ans.size() == tickets.size() + 1)
			return true;
		else
			return false;
	}
	vector<string> findItinerary(vector<vector<string>>& tickets) {
		vector<string> ans;
		vector<bool> visited(tickets.size(), false);
		ans.push_back("JFK");
		findNextStation(tickets, "JFK", ans, visited);
		return ans;
	}
};

int main()
{
	Solution sol;
	vector<vector<string>> test = {{"EZE", "TIA"}, {"EZE", "HBA"}, {"AXA", "TIA"}, {"JFK", "AXA"}, 
		{"ANU", "JFK"}, {"ADL", "ANU"}, {"TIA", "AUA"}, {"ANU", "AUA"}, {"ADL", "EZE"}, {"ADL", "EZE"}, 
		{"EZE", "ADL"}, {"AXA", "EZE"}, {"AUA", "AXA"}, {"JFK", "AXA"}, {"AXA", "AUA"}, {"AUA", "ADL"}, 
		{"ANU", "EZE"}, {"TIA", "ADL"}, {"EZE", "ANU"}, {"AUA", "ANU"}};
	sol.findItinerary(test);
	cout << endl;
}
